Median filtering is a non-linear signal-enhancement technique for the smoothing of signals, the suppression of impulse noise, and preserving of edges. It involves sliding a window having an odd number of elements along the signal and replacing the center sample by the median of the samples in the window. The median value m of the samples in a window is the value for which half of the samples in the window have smaller values than m and the other half have values greater than m. In a one-dimensional median filter having three samples P1, P2, P3, the median value is found by sorting the three samples and selecting the midpoint as the median. In the straightforward approach P2 is compared to P3 in the first stage; the minimum of that is compared to P1 in the second stage; and the minimum of the second stage is the minimum value PMIN. In the third stage the maximum output of the second stage is compared to the maximum of the first stage. The maximum output of the third stage is the maximum value PMAX and the minimum output of the third stage is the median value PMED.
One shortcoming of this approach is that the three stages operate sequentially; it requires three cycles of operation to obtain the median. Another problem is that each sort operation (finding the min and max between two samples) is dependent on the result of the previous operation which, in a deeply pipelined machine, would cause pipeline stall: the pipeline would stop, waiting for the offending instruction to finish, before execution resumes. A fully parallel solution that mitigates the multiple sequential operation problem uses a dedicated ASIC, but this approach entails additional limited-functionality hardware which permanently accompanies the device (e.g., a DSP chip) even though it may be only occasionally needed. Attempts to apply within the device a parallel solution optimized for multiply-accumulate actions (as occur in FIR and FFT operations) has not been pursued because, in a typical device utilizing median filters, the compute-unit result bus has only half the width of the input bus. This is because in multiplication of two N-bit numbers, the result being stored to memory is one number of N bits; but in median filters, the inputs are merely sorted, which results in the same number of outputs.
Additionally, conventional median filters only process new samples and do not include any feedback path to receive a filter-processed sample back as an input for additional or refined filtering.